package com.clstu.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 研究哈夫曼树(wpl最小的二叉树)的模拟和使用
 */
public class HuffManTreeDemo {
    public static void main(String[] args) {
         int[] arr = {13,7,8,29,6,1};
        Node huffmanTree = createHuffmanTree(arr);
        preOrder(huffmanTree);
    }

    //编写方法根据数组创建哈夫曼树
    public static Node createHuffmanTree(int [] arr){
        //先将所有的节点创建好放入ArrayList中便于使用
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            nodes.add(new Node(arr[i]));
        }
        //循环创建哈夫曼树
        while (nodes.size()>1){
            //每次都要排序
            Collections.sort(nodes);
            //拿出两个最小的组成二叉树再放回去
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            Node parent = new Node(left.value + right.value);
            parent.left = left;
            parent.right = right;
            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);
        }
        //返回二叉树的根节点
        return nodes.get(0);
    }

    //编写方法调用前序遍历二叉树
    public static void preOrder(Node root){
        //先判断是否树空
        if(root == null){
            System.out.println("该二叉树为空");
            return;
        }
        root.preOrder();
    }
}

/**
 * 创建节点类
 * 为了便于再ArrayList中可以排序,实现Comparable接口
 */
class Node implements Comparable<Node>{
    int value;//权值
    Node left;//左节点
    Node right;//右节点

    //构造器
    public Node(int value){
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }


    @Override
    public int compareTo(Node o) {
        //从小到大排序,自己在前就是小在前
        return this.value - o.value;
    }

    //编写方法前序变量二叉树
    public void preOrder(){
        //前序遍历 : 自己 ----> 左递归 ---> 右递归
        System.out.println(this);
        if(left!=null){
            left.preOrder();
        }
        if(right!=null){
            right.preOrder();
        }
    }
}